package com.killer;

/**
 * @author ：Killer
 * @date ：Created in 21-4-27 上午10:18
 * @description：${description}
 * @modified By：
 * @version: version
 */
public class GoldDemo {


    public static void main(String[] args) {
        int[] needs = {2, 3, 4, 4, 5};
        int[] values = {400, 200, 300, 400, 500};
        int max=5;
        System.out.println(maxValue(needs, values, max));
    }

    /**
     * 算出最佳工人分配挖矿的策略
     * @param needs  每座金矿各需要的工人人数
     * @param values  每座金矿各自的价值
     * @param max   总工人数
     * @return  收益
     */
    public static int maxValue(int[] needs,int[] values,int max){
        //如果没有金矿,则肯定是0
        if (needs == null || needs.length == 0) {
            return 0;
        }
        if (values == null || values.length == 0) {
            return 0;
        }
        //两个数组容量不等证明数据输入有误
        if (needs.length != values.length) {
            return 0;
        }
        //没有工人直接返回0
        if (max == 0) {
            return 0;
        }
        //构建dp数组(注意要考虑0个工人和0个金矿可选的情况,即边界情况,因此长度分别是needs+1和max+1)
        int[][] dp=new int[needs.length+1][max+1];
        //可以选择的金矿数
        int i;
        //可以选择的工人数
        int j;
        //遍历金矿(从只有1个金矿可选到所有金矿可选)
        for(i=1;i<needs.length+1;i++) {
            //遍历工人(从只有1个工人可选到所有工人可选)
            for(j=1;j<max+1;j++) {
                //这里注意,由于是从1开始遍历,所以取数时要对应的减去1
                if(needs[i-1]>j){
                    //如果该做金矿超过了可选工人总数,那么有这座金矿的选择和没这座金矿的选择它的总收益其实是一模一样的
                    dp[i][j]=dp[i-1][j];
                }else{
                    //如果该金矿可选,且没选的情况,总收益那么跟该金矿不能选是一样的
                    int noChoice=dp[i-1][j];
                    //如果该金矿可选,且选了,那么总收益就是这座金矿的收益+上一个状态下(该金矿不可选)
                    // 扣除了这座金矿需要的工人(用于分配给这座金矿)的收益
                    int choice=values[i-1]+dp[i-1][j-needs[i-1]];
                    //两者取最大值
                    dp[i][j] = Math.max(noChoice, choice);
                }
            }
        }
         //可选工人
        int j=max;
        //输出方案(在所有工人可选的情况下)
        for(int i=needs.length;i>=1;i--) {
            //对比dp[i][j]和dp[i-1][j]
            if (dp[i][j] > dp[i - 1][j]) {
                //如果多一座金矿可选的情况下总收益大于这座金矿不可选,则证明这座金矿是肯定选了
                System.out.println("分配了"+needs[i-1]+"个工人进行对金矿"+i+"的挖掘,产生了"+values[i-1]+"收益");
                //这个时候可分配工人要减少(因为这部分工人已经分配了)
                j = j - needs[i - 1];
            }
        }
        return dp[needs.length][max];
    }

}
